class MinHeap {
  constructor() {
    this.data = [];
  }
  compare(a,b){
    return a - b;
  }
  insert(val){
    this.data.push(val);
    this.shiftUp();
  }
  size(){
    return this.data.length;
  }
  deleteMin(){
    if(this.size()){
      let res = this.data[0];
      if(this.size() > 1){
        this.shiftDown();
      }else{
        this.data = [];
      }
      return res;
    }else {
      return null;
    }
  }
  peek(){
    if(this.size()){
      return this.data[0]
    }else {
      return null;
    }
  }
  shiftUp(){
    let child_index = this.data.length - 1;//>0
    let parent_index = null;//>= 0
    while (child_index > 0){
      parent_index = (child_index -1)/2;
      if(this.compare(this.data[child_index],this.data[parent_index]) < 0){
        this.swap(child_index,parent_index);
        child_index = parent_index;
      }else {
        break;
      }
    }
  }
  shiftDown(){
    this.data[0] = this.data[this.size() - 1];
    this.data.pop();
    let min_index = 0;
    let left_index = 2 * min_index + 1;
    let right_index = 2 * min_index + 2;
    let temp = null;
    while (left_index < this.size()){
      if(right_index < this.size()){
        if(this.compare(this.data[left_index],this.data[right_index]) < 0){
          temp = left_index;
        }else {
          temp = right_index;
        }
      }else{
        temp = left_index;
      }
      if(this.compare(this.data[min_index],this.data[temp]) > 0){
        this.swap(min_index,temp);
        min_index = temp;
        left_index = 2 * min_index + 1;
        right_index = 2 * min_index + 2;
      }
    }
  }
  swap(i,j){
    [this.data[i],this.data[j]] = [this.data[j],this.data[i]]
  }
}
let min_heap = new MinHeap();
for (let num of [4, 5, 8, 2]) {
  min_heap.insert(num);
}

console.log(min_heap)
console.log(min_heap.size())
min_heap.deleteMin();
console.log(min_heap)
/*[4, 5, 8, 2]*/
